// Created by WXX on 2021/9/22 9:11
#include "MyLinkedList.h"

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了79.33%的用户
 * 内存消耗：8.7 MB, 在所有 C++ 提交中击败了19.00%的用户
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {

        int n = 0;
        for (auto p = head; p; p = p->next) n++;

        vector<ListNode*> res;
        auto p = head;
        for (int i = 0; i < k; i++) {
            int len = n / k;
            if (i + 1 <= n % k) len++;
            res.push_back(p);
            for (int j = 0; j < len - 1; j++) p = p->next;
            if (p) {
                auto q = p->next;
                p->next = NULL;
                p = q;
            }
        }
        return res;
    }
};

int main() {

    ListNode *head = MyLinkedList({1, 2, 3}).getHead();
    vector<ListNode*> res = Solution().splitListToParts(head, 5);
    for (auto t : res) MyLinkedList().printLinkedList(t);

    return 0;
}
